package pers.sloera.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * 摘樱桃
 *
 * @author sloera
 * @date 2022-07-10 10:30:12
 */
class CherryPickup {
    public static void main(String[] args) {
        Solution solution = new CherryPickup().new Solution();
        int[][] grid = {{0, 1, -1}, {1, 0, -1}, {1, 1, 1}};
        // int[][] grid = {{1, 1, -1}, {1, -1, 1}, {-1, 1, 1}};
        // int[][] grid = {{1}};
        System.out.println(solution.cherryPickup(grid));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private Map<String, Integer> memo = new HashMap<>();
        private int MIN_VALUE = -50;

        /**
         * 寻找最多能捡到的樱桃
         * <p/>
         * <ul>
         *     <li>dp[n-1][n-1]，可以由dp[n-2][n-1]和dp[n-1][n-2]得到</li>
         *     <li>但是从(0,0)到(n-1,n-1)的过程会影响从(n-1,n-1)到(0,0)的过程，所以需要用到两个dp</li>
         *     <li>dp[i][j]为(0,0)到(i,j)时，最多的点</li>
         *     <li>dpRev[i][j]为(i,j)到(0,0)时，最多的点。实际上是重复一次当前grid下的dp[i][j]</li>
         *     <li>很明显，子矩阵存在重复的情况，所以可以用备忘录来存</li>
         * </ul>
         */
        public int cherryPickup(int[][] grid) {
            int cherryNum = cherryPickup(copyGrid(grid, grid.length - 1, grid[0].length - 1), grid.length - 1, grid[0].length - 1, false);
            if (cherryNum < 0) {
                return 0;
            }
            return cherryNum;
            // 第一次的dp
            // int[][] dp = new int[grid.length][grid[1].length];
            // 第二次的dp，从右下到左上和从左上到右下是一样的
            // int[][] dpRev = new int[grid.length][grid[1].length];
        }

        private int[][] copyGrid(int[][] grid, int i, int j) {
            int[][] ints = new int[i + 1][j + 1];
            for (int k = 0; k <= i; k++) {
                for (int l = 0; l <= j; l++) {
                    ints[k][l] = grid[k][l];
                }
            }

            return ints;
        }

        /**
         * 从(0,0)走到(x,y)往返的最大值
         */
        private int cherryPickup(int[][] grid, int x, int y, boolean shouldCache) {
            int sum = 0;
            if (grid[x][y] == -1) {
                return MIN_VALUE;
            }
            String key = getKey(grid, x, y);
            // if (memo.containsKey(key)) {
            //     return memo.get(key);
            // }
            if (x == 0) {
                for (int i = 0; i <= y; i++) {
                    if (grid[0][y] == -1) {
                        return MIN_VALUE;
                    }
                    sum += grid[0][y];
                    if (grid[0][y] == 1) {
                        grid[0][y] = 0;
                    }
                }
                memo.put(key, sum);
                return sum;
            } else if (y == 0) {
                for (int i = 0; i <= x; i++) {
                    if (grid[x][0] == -1) {
                        return MIN_VALUE;
                    }
                    sum += grid[x][0];
                    if (grid[x][0] == 1) {
                        grid[x][0] = 0;
                    }
                }
                memo.put(key, sum);
                return sum;
            }

            int[][] gridUpUp = copyGrid(grid, x, y);
            int upUp = cherryPickup(gridUpUp, x - 1, y, false) + cherryPickup(gridUpUp, x - 1, y, true);
            int[][] gridUpLeft = copyGrid(grid, x, y);
            int upLeft = cherryPickup(gridUpLeft, x - 1, y, false) + cherryPickup(gridUpLeft, x, y - 1, true);
            int[][] gridLeftLeft = copyGrid(grid, x, y);
            int leftLeft = cherryPickup(gridLeftLeft, x, y - 1, false) + cherryPickup(gridLeftLeft, x, y - 1, true);
            int[][] gridMax;
            int max;
            if (upUp > upLeft) {
                gridMax = gridUpUp;
                max = upUp;
            } else {
                gridMax = gridUpLeft;
                max = upLeft;
            }
            if (leftLeft > max) {
                max = leftLeft;
                gridMax = gridLeftLeft;
            }
            int carry = 0;
            if (gridMax[x][y] == 1) {
                gridMax[x][y] = 0;
                carry = 1;
            }
            for (int i = 0; i < gridMax.length; i++) {
                for (int j = 0; j < gridMax[0].length; j++) {
                    grid[i][j] = gridMax[i][j];
                }
            }
            if (shouldCache) {
                key = getKey(grid, x, y);
                memo.put(key, max + carry);
            }
            return max + carry;
        }

        private String getKey(int[][] grid, int x, int y) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i <= x; i++) {
                for (int j = 0; j <= y; j++) {
                    stringBuilder.append(grid[i][j]);
                }
            }
            String s = stringBuilder.toString();
            return s;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
